'''
@author: Kevin Zhao
@data:Jan 4,2012 
@note:
Selection in linear time

Exercise 9.2-3
'''
import random

def exchange(A_index, B_index, array):
    temp = array[A_index]
    array[A_index] = array[B_index]
    array[B_index] = temp
def partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            i += 1
            exchange(i, j, A)
    exchange(r, i + 1, A)
    return i + 1

def randomized_partition(A, p, r):
    pivot = random.randint(p, r)
    exchange(pivot,r,A)
    return partition(A, p, r)
            
'''
Iterative version of randomized selection algorithm
Input:Array-A,startIndex:p,endIndex:r,the ith order of the desired element
output:the desired element at ith order of the array
'''
def randomized_selection_iterative(A, p, r, i):
    if i < 0:
        return "WARNING:randomized_selection_iterative(A, p, r, >i<)   i should be in range 1<=i<=N"
    while 1:
        if p == r:
            return A[p]
        q = randomized_partition(A, p, r)
#        q = partition(A, p, r)
        k = q - p + 1
        if i == k:
            return A[q]
        elif i < k:
            r = q - 1
        else:
            p = q + 1
            i = i - k
            
A = [13,19,9,5,12,8,7,4,21,2,6,11]
p = 0
r = len(A) - 1
i = 1
print randomized_selection_iterative(A, p, r, 1)
print randomized_selection_iterative(A, p, r, 2)
print randomized_selection_iterative(A, p, r, 3)
print randomized_selection_iterative(A, p, r, 4)
print randomized_selection_iterative(A, p, r, 5)
print randomized_selection_iterative(A, p, r, 6)
print randomized_selection_iterative(A, p, r, 7)
print randomized_selection_iterative(A, p, r, 8)
print randomized_selection_iterative(A, p, r, 9)


            
            
            
